package com.mlh.binarytree;
import java.util.Deque;
import java.util.LinkedList;


/**
 * @author 缪林辉
 * @date 2024/3/27 11:56
 * @DESCRIPTION
 */
// 给定二叉树的根节点 root ，返回所有左叶子节点val之和。
public class SumOfLeftLeaves {
    //利用bfs改的 执行时间10%
    //当然也可以用dfs
    public int method1(TreeNode root) {
        if(root==null){return 0;}
        Deque<TreeNode> treeNodes = new LinkedList<>();
        Deque<Integer> flagQueue=new LinkedList<>();//这个队列用来记录入队节点是左节点还是右节点
        int leftNum=0;//左叶子节点val和
        treeNodes.add(root);
        flagQueue.add(-1);//根节点没有左右节点之分，用-1表示
        while(!treeNodes.isEmpty()){
            int len=treeNodes.size();
            while (len>0){
                TreeNode node=treeNodes.poll();
                int flag=flagQueue.poll();
                int flag2=0;//用于判断该节点是否是叶子节点
                len--;
                if(node.left!=null){
                    treeNodes.add(node.left);
                    flagQueue.add(1);//左节点用1表示
                    flag2=1;
                }
                if(node.right!=null){
                    treeNodes.add(node.right);
                    flagQueue.add(0);//右节点用0表示
                    flag2=1;
                }
                if(flag2==0&&flag==1){//左节点且是叶子节点就是我们的目标节点
                    leftNum+=node.val;
                }
            }
        }
        return leftNum;
    }
}
